/*
 * @lc app=leetcode.cn id=558 lang=cpp
 *
 * [558] 四叉树交集
 */

#include "include.h"

class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};

// @lc code=start
/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* intersect(Node* quadTree1, Node* quadTree2) {
        // 两个二进制矩阵进行 按位逻辑或运算
        ;
        Node* res = nullptr;
        operation(quadTree1, quadTree2, res);
        return res;
    }
    void operation(Node* quadTree1, Node* quadTree2, Node*& newQuadTree){
        if (quadTree1 == nullptr and quadTree2 == nullptr){return;}
        
        newQuadTree = new Node;
        
        if (quadTree1->isLeaf and quadTree2->isLeaf){
// printf("all leaf %d %d\n", quadTree1->val, quadTree2->val);
            newQuadTree->isLeaf = true;
            newQuadTree->val = quadTree1->val or quadTree2->val;
            return;
        }
        if (!quadTree1->isLeaf and !quadTree2->isLeaf){
// printf("all not leaf \n");
            newQuadTree->isLeaf = false;
            operation(quadTree1->topLeft, quadTree2->topLeft, newQuadTree->topLeft);
            operation(quadTree1->topRight, quadTree2->topRight, newQuadTree->topRight);
            operation(quadTree1->bottomLeft, quadTree2->bottomLeft, newQuadTree->bottomLeft);
            operation(quadTree1->bottomRight, quadTree2->bottomRight, newQuadTree->bottomRight);
            // check re merge ???
            checkAllSame(newQuadTree);
            return;
        }

        // Node* sonTopLeft = new Node;
        // Node* sonTopRight = new Node;
        // Node* sonBottomLeft = new Node;
        // Node* sonBottomRight = new Node;
        // newQuadTree->topLeft = sonTopLeft;
        // newQuadTree->topRight = sonTopRight;
        // newQuadTree->bottomLeft = sonBottomLeft;
        // newQuadTree->bottomRight = sonBottomRight;

        // 2 root - 1 leaf
        if (quadTree1->isLeaf and !quadTree2->isLeaf){
// printf("2 root - 1 leaf\n");

            if (quadTree1->val == true){
                // one all true => result all true
                newQuadTree->isLeaf = true;
                newQuadTree->val = true;
            } else{
                // one all false => result depends on the other ~
                copyQuadTree(quadTree2, newQuadTree);
            }

            // newQuadTree->isLeaf = false;
            // helper(quadTree2->topLeft, quadTree1->val, newQuadTree->topLeft);
            // helper(quadTree2->topRight, quadTree1->val, newQuadTree->topRight);
            // helper(quadTree2->bottomLeft, quadTree1->val, newQuadTree->bottomLeft);
            // helper(quadTree2->bottomRight, quadTree1->val, newQuadTree->bottomRight);
            // // re merge ???
        }
        // 1 root - 2 leaf
        else{
// printf("1 root - 2 leaf\n");

            if (quadTree2->val == true){
                // one all true => result all true
                newQuadTree->isLeaf = true;
                newQuadTree->val = true;
            } else{
                // one all false => result depends on the other ~
                copyQuadTree(quadTree1, newQuadTree);
            }
            // // helper(quadTree1, quadTree2->val, newQuadTree);
            // helper(quadTree1->topLeft, quadTree2->val, newQuadTree->topLeft);
            // helper(quadTree1->topRight, quadTree2->val, newQuadTree->topRight);
            // helper(quadTree1->bottomLeft, quadTree2->val, newQuadTree->bottomLeft);
            // helper(quadTree1->bottomRight, quadTree2->val, newQuadTree->bottomRight);
        }
    }
    void copyQuadTree(Node* source, Node*& copy){
        if (source == nullptr){return;}
// printf("copy\n");
        if (copy == nullptr){copy = new Node;}
        copy->isLeaf = source->isLeaf;
        copy->val = source->val;

        copyQuadTree(source->topLeft, copy->topLeft);
        copyQuadTree(source->topRight, copy->topRight);
        copyQuadTree(source->bottomLeft, copy->bottomLeft);
        copyQuadTree(source->bottomRight, copy->bottomRight);
    }
    inline void checkAllSame(Node*& quadTree){
        if (quadTree->isLeaf == false){
            if (quadTree->topLeft->isLeaf and
                quadTree->topRight->isLeaf and
                quadTree->bottomLeft->isLeaf and
                quadTree->bottomRight->isLeaf){
                if (quadTree->topLeft->val == quadTree->topRight->val and
                    quadTree->topLeft->val == quadTree->bottomLeft->val and
                    quadTree->topLeft->val == quadTree->bottomRight->val){
// printf("all same %d\n", quadTree->val);
                    quadTree->isLeaf = true;
                    quadTree->val = quadTree->topLeft->val;
                    delete quadTree->topLeft;
                    delete quadTree->topRight;
                    delete quadTree->bottomLeft;
                    delete quadTree->bottomRight;
                    quadTree->topLeft = nullptr;
                    quadTree->topRight = nullptr;
                    quadTree->bottomLeft = nullptr;
                    quadTree->bottomRight = nullptr;
                }
            }
        }
    }

    void helper(Node* quadTree, bool val, Node*& newQuadTree){
        newQuadTree = new Node;

        if (quadTree->isLeaf){
printf("to leaf %d %d\n", quadTree->val, val);
            newQuadTree->isLeaf = true;
            newQuadTree->val = quadTree->val or val;
        }else{
printf("not end : %d %d %d %d | %d\n",
quadTree->topLeft,
quadTree->topRight,
quadTree->bottomLeft,
quadTree->bottomRight,
val
);
            // Node* sonTopLeft = new Node;
            // Node* sonTopRight = new Node;
            // Node* sonBottomLeft = new Node;
            // Node* sonBottomRight = new Node;
            // newQuadTree->topLeft = sonTopLeft;
            // newQuadTree->topRight = sonTopRight;
            // newQuadTree->bottomLeft = sonBottomLeft;
            // newQuadTree->bottomRight = sonBottomRight;

            helper(quadTree->topLeft, val, newQuadTree->topLeft);
            helper(quadTree->topRight, val, newQuadTree->topRight);
            helper(quadTree->bottomLeft, val, newQuadTree->bottomLeft);
            helper(quadTree->bottomRight, val, newQuadTree->bottomRight);
        }
    }
};
// @lc code=end

// [[0,0],[1,0],[1,0],[1,1],[1,1]]
// [[0,0],[1,1],[1,1],[1,0],[1,1]]

// [[0,0],[1,0],[1,0],[1,1],[1,1]]\n[[0,0],[1,1],[1,1],[1,0],[1,1]]

// [[0,0],[1,1],[1,0],[1,1],[1,1]]\n[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
